AVL_Tree<Type>\f1 A parameterized, height-balanced binary tree class
.SH SYNOPSIS
#include <cool/AVL_Tree.h>
.SH DESCRIPTION
The
AVL_Tree< Type >
class implements height-balanced, dynamic, binary trees.
The
AVL_Tree< Type >
class is publicly derived from the
Binary_Tree< Type >
class,
and both are parameterized over some
Type .
An AVL tree is a compromise between
the expense of a fully balanced binary tree and the desire for efficient search
times for both average and worst-case scenarios. As a result, an AVL tree maintains a binary tree that is height-balanced, ensuring that the difference
between the depth of the left subtree and right subtree for every node is no
more than one.
.PP
The
AVL_Tree< Type >
class implements the notion of a current position. This is
useful for iterating through the nodes of a tree. The current position is
maintained in a data member of type
AVL_Tree_state
and is set or reset by all
member functions affecting elements in the class. Member functions are provided
to reset the current position, move to the next and previous elements, find an
element, and get the value at the current position. The \f3Iterator<Type>\f1 class
provides a mechanism to save and restore the state associated with the current
position, thus allowing the programmer to use multiple iterators over the same
instance of a tree.
.PP
The
AVL_Tree< Type >
class inherits all its member functions publicly from the
Binary_Tree< Type >
class. The only member functions that are overloaded are
those that affect the structure of the tree, thus potentially requiring one or